package Heap;

    use strict;
    use warnings;

    my @Instances = ();

    sub new {
        my ($Caller, %args) = @_;
        my $Class = ref $Caller || $Caller;
        my $self = bless { }, $Class;

        if (exists $args{list}) {
            my @list = @{ $args{list} };
            $self->{list} = \@list; }
        else {
            $self->{list} = []; }

        $self->{heapsize} = $#{ $self->{list} };

        $self->{heaptype} = exists $args{heaptype} ? $args{heaptype} : "max";
        $self->{heaptype} = "max" if $self->{heaptype} !~ m/min/;

        # Tests for max or min on heaptype attribute, and sets a reference
        # to the appropriate heapify function.
        $self->{heapfunc} = $self->{heaptype} =~ m/^max$/ ? \&maxHeapify : \&minHeapify;

        push @Instances, $self;

        $self->buildHeap;

        return $self;  }

    #+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*#

    sub getAllInstances {
        my ($Caller, %args) = (@_);
        my $Class = ref $Caller || $Caller;

        return grep{ $_->isa($Class) } @Instances unless undef;
        return "Empty!";    }

    sub setList {
        my $self = shift;
        my $list = shift;
        my @listCopy = @$list;
        $self->{list} = \@listCopy;
        $self->{heapsize} = $#listCopy;
        $self->buildHeap();    }

    sub getList {
        my $self = shift;
        return $self->{list};    }

    sub printList {
        my $self = shift;
        return "[".join(', ', map{"($_->[0], $_->[1])"} @{ $self->{list} })."]";    }

    sub setHeapsize {
        my $self = shift;
        $self->{heapsize} = shift;  }

    sub getHeapsize {
        my $self = shift;
        return $self->{heapsize};   }

    sub setHeaptype {
        my $self = shift;
        my $type = shift;
        if ($type =~ m/^max$/ || $type =~ m/^min$/) {
            $self->{heaptype} = $type;  }
        else {
            $self->{heaptype} = 'max';  }
        if ( $self->{heaptype} =~ m/^max$/ ) {
            $self->{heapfunc} = \&maxHeapify;   }
        else {
            $self->{heapfunc} = \&minHeapify;   }
        $self->buildHeap;   }

    sub getHeaptype {
        my $self = shift;
        return $self->{heaptype};   }

    sub getHeapfunc {
        my $self = shift;
        return $self->{heapfunc};   }

    #+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*#

    sub heapPush {
        my $self = shift;
        my $element = shift;
        $self->heapInsert($element);   }

    sub heapPop {
        my $self = shift;

        $self->swap(0, $self->{heapsize});
        my $element = pop @{$self->{list}};
        $self->{heapsize} -= 1;
        my $function = $self->{heapfunc};
        $function->($self, 0);
        return $element;    }

    sub heapInsert {
        my $self = shift;
        my $element = shift;
        push @{ $self->{list} }, 0+"inf";
        $self->{heapsize} += 1;
        $self->heapIncreasePriority($self->{heapsize}, $element);   }

    sub heapIncreasePriority{
        my $self = shift;
        my ($i, $element) = (@_);


        $self->setValue($i, $element);

        if ($self->getHeaptype =~ m/^max$/) {
            while ($i > 0 && @{ $self->getValue($self->getParent($i)) }[1] < @{ $self->getValue($i) }[1]) {
                $self->swap($i, $self->getParent($i));
                $i = $self->getParent($i);  }   }
        else {
            while ($i > 0 && @{ $self->getValue($self->getParent($i)) }[1] > @{ $self->getValue($i) }[1]) {
                $self->swap($i, $self->getParent($i));
                $i = $self->getParent($i);  }   }   }

    #+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*#

    sub swap {
        my $self = shift;
        my ($a, $b) = (@_);

        @{$self->{list}}[$a, $b] = @{$self->{list}}[$b, $a];    }

    sub setValue {
        my $self = shift;
        my ($index, $value) = (@_);
        $self->{list}->[$index] = $value;    }

    sub getValue {
        my $self = shift;
        my $index = shift;
        return $self->{list}->[$index];    }

    #*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*#

    sub getParent {
        my $self = shift;
        my $index = shift;
        return int(($index - 1) / 2);   }

    sub getLeft {
        my $self = shift;
        my $index = shift;
        return ($index * 2) + 1;    }

    sub getRight {
        my $self = shift;
        my $index = shift;
        return ($index * 2) + 2;    }


    #*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*#
    #*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*#
    #*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*#


    sub buildHeap {
        my $self = shift;

        if (scalar @_ != 0) {
            my $list = shift;
            if (ref($list) =~ m/ARRAY/) {
                $self->setList($list);  }   }

        elsif (scalar $self->{list} == 0) {
            return $self->{list};   }

        my $heapfunc = $self->{heapfunc};

        for my $index ( -int(($self->{heapsize}) / 2) .. 0 ) {
            $heapfunc->($self, -$index);   }    }

    sub maxHeapify {
        my $self = shift;
        my $index = shift;

        my $heapsize = $self->{heapsize};
        my $largest;
        my $left = $self->getLeft($index);
        my $right = $self->getRight($index);

        if ($left <= $heapsize && @{ $self->getValue($left) }[1] > @{ $self->getValue($index) }[1]) {
            $largest = $left;   }
        else {
            $largest = $index;  }

        if ($right <= $heapsize && @{ $self->getValue($right) }[1] > @{ $self->getValue($largest) }[1]) {
            $largest = $right;  }

        if ($index != $largest) {
            $self->swap($index, $largest);
            $self->maxHeapify($largest);
            return; }   }

    sub minHeapify {
        my $self = shift;
        my $index = shift;

        my $heapsize = $self->{heapsize};
        my $smallest;
        my $left = $self->getLeft($index);
        my $right = $self->getRight($index);

        if ($left <= $heapsize && @{ $self->getValue($left) }[1] < @{ $self->getValue($index) }[1]) {
            $smallest = $left;   }
        else {
            $smallest = $index;  }

        if ($right <= $heapsize && @{ $self->getValue($right) }[1] < @{ $self->getValue($smallest) }[1]) {
            $smallest = $right;  }

        if ($index != $smallest) {
            $self->swap($index, $smallest);
            $self->minHeapify($smallest);
            return; }   }

    sub destroy {
        my $self = shift;
        @Instances = grep{ $_ != $self } @Instances;    }

    # Class end
    1;
